package com.example;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author loubobooo
 * @Description #46. 全排列
 * @Date 2020/1/19
 */
public class Permutations {

    private List<List<Integer>> lists = new LinkedList<>();

    /**
     * @Author loubobooo
     * @Description 给定一个没有重复数字的序列，返回其所有可能的全排列。
     * 示例:
     * 输入: [1,2,3]
     * 输出:
     * [
     *   [1,2,3],
     *   [1,3,2],
     *   [2,1,3],
     *   [2,3,1],
     *   [3,1,2],
     *   [3,2,1]
     * ]
     * @Date 2020/1/19 10:05
     * @Param
     * @return
     **/
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> list = new LinkedList<>();
        backtrack(nums, list);
        return lists;
    }

    private void backtrack(int[] nums, LinkedList<Integer> list){
        // 触发结束条件
        if(list.size() == nums.length){
            // 注意：变量所指向的对象在递归的过程中只有一份，即值传递。因此需要new LinkedList放入list，不然list都为空
            lists.add(new LinkedList<>(list));
            return;
        }
        for(int i = 0, length = nums.length; i < length; i++){
            if(list.contains(nums[i])){
                continue;
            }
            // 做选择
            list.add(nums[i]);
            // 回溯
            backtrack(nums, list);
            // 注意：撤销上一步的选择，即回退
            list.removeLast();
        }
    }


}
